# a+b+c=1000，a2+b2=c2(2是平方)
import threading
import time


# 方案一：穷举a、b、c ∈ [0,1000]->判断a2+b2=c2 & a+b+c=1000
def func1():
    start_time = time.time()
    for a in range(0, 1001):
        for b in range(0, 1001):
            for c in range(0, 1001):
                if a * a + b * b == c * c and a + b + c == 1000:
                    print(a, b, c)
    print('func1', time.time() - start_time)


# 方案二：穷举a、b ∈ [0,1000]->确定c=(a+b+c)-a-b->判断a2+b2=c2，减少一层循环
def func2():
    start_time = time.time()
    for a in range(0, 1001):
        for b in range(0, 1001):
            c = 1000 - a - b
            if a * a + b * b == c * c:
                print(a, b, c)
    print('func2', time.time() - start_time)


# 方案三：方案二改进->利用a+b+c=1000，确定了a，则b<1000-a,可以缩小第二层循环的循环次数
def func3():
    start_time = time.time()
    for a in range(0, 1001):
        num = 1000 - a
        for b in range(0, num + 1):
            c = num - b
            if a * a + b * b == c * c:
                print(a, b, c)
    print('func3', time.time() - start_time)


"""
方案四：更换思路->a、b、c互相影响，但a、b是两个变量，c只是一个变量，可以先确定c，
       再确定a、b。而且经过思考，c的取值范围是最小的，因为abc的关系可以构成
       直角三角形，那么有c>a & c>b & max_c = max_a = max_b = (a+b+c)/2
       且c2=a2+b2>=2ab,c2=min_c2=2ab <=> a=b,那么min_c2=2ab=2a2=2b2
       那么min_c=(根号2)*a=(根号2)*b => a=b=(根号2/2)*min_c => 
       a+b+min_c=(1+根号2)*min_c=a+b+c => min_c=(a+b+c)/(1+根号2)
       => min_c=(根号2-1)*(a+b+c)，那么c的取值范围长度=(1.5-根号2)*(a+b+c)
       约等于0.086*(a+b+c),a、b的取值不能超过c，那么a、b取值范围长度∈[min_c,max_c]
       约等于[0.414,0.5]*(a+b+c),那么c的取值范围是最小的，外层循环先确定c可以大大减少
       循环次数，提高效率。
       综上，c ∈ [min_c,max_c]=[(根号2-1)*(a+b+c),(a+b+c)/2]
       a、b ∈ [0,c], b的某一次取值b1 = (a+b+c)-a1-c1，
       再判断a1，b1，c1是否符合条件
"""


def func4():
    start_time = time.time()
    for c in range(int(1000 * (2 ** 0.5 - 1)), 501):
        for a in range(0, c + 1):
            b = 1000 - a - c
            if a * a + b * b == c * c:
                print(a, b, c)
    print('func4', time.time() - start_time)


"""
方案五：方案四改进->a1=(a+b+c)-b1-c1=(a+b+c)/2-b1+(a+b+c)/2-c1>=(a+b+c)/2-c1
      0<=a,b,c<=(a+b+c)/2,b1未知，c1已知，那么用(a+b+c)/2-c1作为a的取值下限比0
      更好，进一步缩小取值范围,理论上较方案四略微提高效率，但和方案四相差不大
      综上，c ∈ [min_c,max_c]=[(根号2-1)*(a+b+c),(a+b+c)/2]
      a、b ∈ [(a+b+c)/2-c,c], b的某一次取值b1 = (a+b+c)-a1-c1，
      再判断a1，b1，c1是否符合条件
"""


def func5():
    start_time = time.time()
    for c in range(int(1000 * (2 ** 0.5 - 1)), 501):
        for a in range(500 - c, c + 1):
            b = 1000 - a - c
            if a * a + b * b == c * c:
                print(a, b, c)
    print('func5', time.time() - start_time)


if __name__ == '__main__':
    func = [func2(), func3(), func4(), func5()]
    for i in range(4):
        t = threading.Thread(func[i])
        t.start()
